typedef long long int64;
int64 n;
int primes[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
int64 gcd(int64 a,int64 b);
int64 mul(int64 a,int64 b,int64 p) {
	int64 y=(int64)((long double)a*(long double)b/(long double)p+1e-7);
	int64 r=a*b-y*p;
	if (r<0) r+=p;
	return r;
}
int64 power(int64 a,int64 b,int64 p); // a^b%p
bool isPrime(int64 n)
{
	if (n == 2) return 1;
	if(n % 2 == 0) return false;
	int64 u = n - 1;
	int t = 0;
	while(u % 2 == 0) {
		t++;
		u /= 2;
	}
	for(int i = 0; i < 15; i++) {
		int64 p = power(primes[i], u, n);
		int64 prev;
		for(int j = 0; j < t; j++)
		{
			prev = p;
			p = mul(p,p,n);
			if(p == 1 && prev != 1 && prev != n-1) return false;
		}
		if(p!=1) return false;
	}
	return true;
}
int64 smallestFactor(int64 n)
{
	if (n<=1000000)
	{
		for (int p=2;p*p <= n;p++)
			if (n%p==0)
				return p;
		return n;
	}
	if (isPrime(n))
		return n;
	for(int ttt = 0; ttt < 5; ttt++)
	{
		int k=2;
		int64 x=rand()%900;
		int64 y=x;
		for (int i=2;i<1000000;i++)
		{
			x=mul(x,x,n);
			if (x==0)
				x=n-1;
			else
				x--;
			int64 t=gcd(x-y<0?y-x:x-y,n);
			if (t!=1 && t!=n)
			{
				int64 r1=smallestFactor(t);
				int64 r2=smallestFactor(n/t);
				return r1<r2?r1:r2;
			}
			if (i==k)
			{
				y=x;
				k=k*2;
			}
		}
	}
	return n;
}
